package com.c2b.algorithm.leetcode.base.monotone_stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/online-stock-span/">股票价格跨度(Online Stock Span)</a>
 * <p>设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。</p>
 * <p>
 * 当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 *     <ul>
 *         <li>例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。</li>
 *     </ul>
 * </p>
 * <p>
 * 实现 StockSpanner 类：
 *     <ul>
 *         <li>StockSpanner() 初始化类对象。</li>
 *         <li>int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。</li>
 *     </ul>
 * </p>
 * <p>示例：</p>
 * <pre>
 * 输入：
 *      ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
 *      [[], [100], [80], [60], [70], [60], [75], [85]]
 * 输出：
 *      [null, 1, 1, 1, 2, 1, 4, 6]
 *
 * 解释：
 *      StockSpanner stockSpanner = new StockSpanner();
 *      stockSpanner.next(100); // 返回 1
 *      stockSpanner.next(80);  // 返回 1
 *      stockSpanner.next(60);  // 返回 1
 *      stockSpanner.next(70);  // 返回 2
 *      stockSpanner.next(60);  // 返回 1
 *      stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
 *      stockSpanner.next(85);  // 返回 6
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= price <= 10^5</li>
 *     <li>最多调用 next 方法 10^4 次</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/6 10:46
 */
public class LC0901OnlineStockSpan_M {

    static class StockSpanner {
        /**
         * 单调栈，在栈中维护比当日价格大的所有值。如果遇到小于等于当日价格的，从栈中弹出，并累加上持续天数。<p>
         * int[]：长度为2，0-价格 1-持续天数
         */
        private final Deque<int[]> stack;

        public StockSpanner() {
            stack = new ArrayDeque<>();
        }

        public int next(int price) {
            // 持续天数
            int lastingDays = 1;
            // 加上之前栈中元素价格小于等于当日价格的持续时间
            while (!stack.isEmpty() && price >= stack.peekLast()[0]) {
                lastingDays += stack.pollLast()[1];
            }
            stack.add(new int[]{price, lastingDays});
            return lastingDays;
        }
    }

    public static void main(String[] args) {
        StockSpanner stockSpanner = new StockSpanner();
        System.out.println(stockSpanner.next(100));
        System.out.println(stockSpanner.next(80));
        System.out.println(stockSpanner.next(60));
        System.out.println(stockSpanner.next(70));
        System.out.println(stockSpanner.next(60));
        System.out.println(stockSpanner.next(75));
        System.out.println(stockSpanner.next(85));
    }
}
